package leetcode_动态规划._07背包问题.完全背包;

/**
 * @author yzh
 * @data 2021/3/19 20:29
 */
public class Sample {
    public static void main(String[] args) {
        System.out.println(new Sample().method2(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }

    public int method1(int[] w, int[] p, int bg) {
        int[] dp = new int[bg + 1];
        dp[0] = 0;
        for (int i = 0; i < w.length; i++) {
            for (int j = w[i]; j <= bg; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        return dp[bg];
    }

    public int method2(int[] w, int[] p, int bg) {
        int[] dp = new int[bg + 1];
        dp[0] = 0;
        for (int i = 1; i <= bg; i++) {
            for (int j = 0; j < w.length; j++) {
                if (i - w[j] >= 0) dp[i] = Math.max(dp[i], dp[i - w[j]] + p[j]);
            }
        }
        return dp[bg];
    }
}
